package com.echo.code.arithmetic.chapter06;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by baiyap on 2018/8/14.
 */
public class BreadthFristSearch {

  public static void main(String[] args) {
    HashMap<String, List<String>> graph = new HashMap<String, List<String>>() {{
      put("you", new LinkedList<>(Arrays.asList("bob", "alice", "claire")));
      put("bob", new LinkedList<>(Arrays.asList("anuj", "peggy")));
      put("alice", new LinkedList<>(Arrays.asList("peggy")));
      put("claire", new LinkedList<>(Arrays.asList("thom", "jonny")));
      put("anuj", new LinkedList<>());
      put("peggy", new LinkedList<>());
      put("thom", new LinkedList<>());
      put("jonny", new LinkedList<>());
    }};

    LinkedList<String> search_queue = new LinkedList<>();
    LinkedList<String> searched = new LinkedList<String>() {{
      add("you");
    }};

    search_queue.addAll(graph.get("you"));
    while (!search_queue.isEmpty()) {
      String person = search_queue.poll();
      if (!searched.contains(person)) {
        if (person_is_seller(person)) {
          System.out.println(person + " is a mango seller!");
          return;
        } else {
          search_queue.addAll(graph.get(person));
          searched.add(person);
        }
      }
    }
    System.out.println("there is no mango seller!");
  }

  private static boolean person_is_seller(String name) {
    return name.endsWith("m");
  }
}
